public class Text3 {
    // 143.重排链表
    public void reorderList(ListNode head) {
        // 1.中间节点
        ListNode slow = head,fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2.逆序后半部分
        ListNode head2 = new ListNode(0);
        ListNode cur = slow.next;
        slow.next = null;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = next;
        }

        // 3.合并
        ListNode cur1 = head, cur2 = head2.next;
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        while(cur1 != null){
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;

            if(cur2 != null){
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
    }
}
